package chapter2;

/**
 * 算法基础-插入排序
 * <p>
 * 原址排序-最坏/平均O(n^2)
 */
public class InsertionSort {

    public static void insertionSort(int[] A) {
        for (int j = 1; j < A.length; j++) {
            // 当前的基点
            int key = A[j];
            int i = j - 1;
            // 从头开始找到比较基点小的数,并后移
            while (i >= 0 && A[i] > key) {
                A[i + 1] = A[i];
                i = i - 1;
            }
            // 将基点插入当前位置
            A[i + 1] = key;
        }
    }

    public static void insertionSort2(int[] A, int n) {
        if (n < 1) {
            return;
        }
        // 递归至数组0
        insertionSort2(A, n - 1);
        // 从数组0开始排序,代表之前都排序好了
        insertion2(A, n);
    }

    public static void insertion2(int[] A, int n) {
        int key = A[n];
        int i = n - 1;
        while (i >= 0 && A[i] > key) {
            A[i + 1] = A[i];
            i = i - 1;
        }
        A[i + 1] = key;
    }

}
